{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count of Interesting Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countInterestingSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计趣味子数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，以及整数 <code>modulo</code> 和整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请你找出并统计数组中 <strong>趣味子数组</strong> 的数目。</p>\n",
    "\n",
    "<p>如果 <strong>子数组</strong> <code>nums[l..r]</code> 满足下述条件，则称其为 <strong>趣味子数组</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在范围 <code>[l, r]</code> 内，设 <code>cnt</code> 为满足 <code>nums[i] % modulo == k</code> 的索引 <code>i</code> 的数量。并且 <code>cnt % modulo == k</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>以整数形式表示并返回趣味子数组的数目。<em> </em></p>\n",
    "\n",
    "<p><span><strong>注意：</strong>子数组是数组中的一个连续非空的元素序列。</span></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,4], modulo = 2, k = 1\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>在这个示例中，趣味子数组分别是： \n",
    "子数组 nums[0..0] ，也就是 [3] 。 \n",
    "- 在范围 [0, 0] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。\n",
    "- 因此 cnt = 1 ，且 cnt % modulo == k 。\n",
    "子数组 nums[0..1] ，也就是 [3,2] 。\n",
    "- 在范围 [0, 1] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。\n",
    "- 因此 cnt = 1 ，且 cnt % modulo == k 。\n",
    "子数组 nums[0..2] ，也就是 [3,2,4] 。\n",
    "- 在范围 [0, 2] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。\n",
    "- 因此 cnt = 1 ，且 cnt % modulo == k 。\n",
    "可以证明不存在其他趣味子数组。因此，答案为 3 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,9,6], modulo = 3, k = 0\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在这个示例中，趣味子数组分别是： \n",
    "子数组 nums[0..3] ，也就是 [3,1,9,6] 。\n",
    "- 在范围 [0, 3] 内，只存在 3 个下标 i = 0, 2, 3 满足 nums[i] % modulo == k 。\n",
    "- 因此 cnt = 3 ，且 cnt % modulo == k 。\n",
    "子数组 nums[1..1] ，也就是 [1] 。\n",
    "- 在范围 [1, 1] 内，不存在下标满足 nums[i] % modulo == k 。\n",
    "- 因此 cnt = 0 ，且 cnt % modulo == k 。\n",
    "可以证明不存在其他趣味子数组，因此答案为 2 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5 </sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= modulo &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt; modulo</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-of-interesting-subarrays](https://leetcode.cn/problems/count-of-interesting-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-of-interesting-subarrays](https://leetcode.cn/problems/count-of-interesting-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4]\\n2\\n1', '[3,1,9,6]\\n3\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        for i,num in enumerate(nums):\n",
    "            if num % modulo == k:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "                \n",
    "       # print(nums)\n",
    "        \n",
    "        n = len(nums)\n",
    "        \n",
    "        arr = []\n",
    "        \n",
    "        t = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                t += 1\n",
    "            else:\n",
    "                arr.append(t)\n",
    "                t = 0\n",
    "        \n",
    "        arr.append(t)\n",
    "        # print(arr)\n",
    "        res = 0\n",
    "        # k = 0 特殊处理       \n",
    "        if not k:\n",
    "            for num in arr:\n",
    "                res += (1+num)*num//2\n",
    "            k += modulo\n",
    "        \n",
    "        \n",
    "        for start in range(k,k+modulo):            \n",
    "            if start - k >= len(arr):\n",
    "                break\n",
    "            \n",
    "            left = arr[start-k]+1    \n",
    "            \n",
    "           # print(start)            \n",
    "            while start < len(arr):                                \n",
    "                res += left * (arr[start]+1)                \n",
    "               # print(start,left,res)                                                \n",
    "                \n",
    "                start += modulo\n",
    "                if start - k >= len(arr):\n",
    "                    break\n",
    "                left += arr[start-k]+1\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        # 0000100010000100100\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        f = []\n",
    "        if modulo == 1:\n",
    "            return len(nums)*(len(nums)+1)//2\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%modulo == k:\n",
    "                f.append(count)\n",
    "                count = 0\n",
    "                continue\n",
    "            count += 1\n",
    "        f.append(count)\n",
    "        # print(f)\n",
    "        v = [1]*len(f)\n",
    "        ans = 0\n",
    "        if k == 0:\n",
    "            k = modulo\n",
    "            for i in f:\n",
    "                ans += i*(i+1)//2\n",
    "        for i in range(len(f)):\n",
    "            if not v[i]:\n",
    "                continue\n",
    "            j = i+k\n",
    "            accu = f[i] + 1\n",
    "            \n",
    "            while j<len(f):\n",
    "                # print(j,accu,ans)\n",
    "                v[j-k] = 0\n",
    "                ans += accu*(f[j]+1)\n",
    "                j += modulo\n",
    "                if j >= len(f):\n",
    "                    break\n",
    "                # print(j,accu,ans)\n",
    "                accu += f[j-k]+1\n",
    "            # print(ans,v)\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        f = []\n",
    "        if modulo == 1:\n",
    "            return len(nums)*(len(nums)+1)//2\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%modulo == k:\n",
    "                f.append(count)\n",
    "                count = 0\n",
    "                continue\n",
    "            count += 1\n",
    "        f.append(count)\n",
    "        # print(f)\n",
    "        v = [1]*len(f)\n",
    "        ans = 0\n",
    "        if k == 0:\n",
    "            k = modulo\n",
    "            for i in f:\n",
    "                ans += i*(i+1)//2\n",
    "        for i in range(len(f)):\n",
    "            if not v[i]:\n",
    "                continue\n",
    "            j = i+k\n",
    "            accu = f[i] + 1\n",
    "            \n",
    "            while j<len(f):\n",
    "                # print(j,accu,ans)\n",
    "                v[j-k] = 0\n",
    "                ans += accu*(f[j]+1)\n",
    "                j += modulo\n",
    "                if j >= len(f):\n",
    "                    break\n",
    "                # print(j,accu,ans)\n",
    "                accu += f[j-k]+1\n",
    "            # print(ans,v)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = [1] + [0] * (n)\n",
    "        res = s = 0\n",
    "        for x in nums:\n",
    "            if x % modulo == k:\n",
    "                s = (s + 1) % modulo\n",
    "            s2 = (s - k + modulo) % modulo\n",
    "            if s2 <= n:\n",
    "                res += cnt[s2]\n",
    "            cnt[s] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:#前缀和，或滑窗\n",
    "        idx=[-1]\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]%modulo==k:\n",
    "                idx.append(i)\n",
    "        idx.append(n)\n",
    "        res=0\n",
    "        if k==0:\n",
    "            for i in range(1,len(idx)):\n",
    "                v=idx[i]-idx[i-1]\n",
    "                # print(i,v)\n",
    "                res+=v*(v-1)//2\n",
    "            k=modulo\n",
    "        elif len(idx)-2<k:return 0\n",
    "            \n",
    "        # print(idx)\n",
    "        dp=[0]*min(len(idx),modulo)\n",
    "        for i in range(1,len(idx)):#-k之前所有的对应位置的和\n",
    "            l=idx[i]-idx[i-1]\n",
    "            if len(dp)>(i-k)%modulo:\n",
    "                res+=dp[(i-k)%modulo]*l\n",
    "            if len(dp)>i%modulo:\n",
    "                dp[i%modulo]+=l\n",
    "            # for j in range(i+k-1,len(idx)-1,modulo):#l/r都包括\n",
    "            #     # print(i,j,modulo,k)\n",
    "            #     r=idx[j+1]-idx[j]\n",
    "            #     res+=l*r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        arr = []\n",
    "        t = 1\n",
    "        # 转化为01数组，并合并每个1前的0的数目(包含1本身)\n",
    "        for i,num in enumerate(nums):\n",
    "            if num % modulo == k:\n",
    "                arr.append(t)\n",
    "                t = 1\n",
    "            else:\n",
    "                t += 1\n",
    "                                                                           \n",
    "        arr.append(t)\n",
    "        # print(arr)\n",
    "        res = 0\n",
    "        # k = 0 特殊处理       \n",
    "        if not k:\n",
    "            # 要去掉1本身，只看0的情况\n",
    "            for num in arr:\n",
    "                res += (num-1)*num//2\n",
    "            # 保证k不等于0\n",
    "            k += modulo\n",
    "        \n",
    "        \n",
    "        for start in range(min(modulo,len(arr))):            \n",
    "            left = arr[start]\n",
    "            while start + k < len(arr):\n",
    "                res += left * arr[start+k]\n",
    "                start += modulo\n",
    "                if start < len(arr):\n",
    "                    left += arr[start]\n",
    "        \n",
    "        return res\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        ids=[i for i,v in enumerate(nums) if v%modulo==k]\n",
    "        ids=[-1]+ids+[len(nums)]\n",
    "        n=len(ids)\n",
    "        dd=[ids[i]-ids[i-1] for i in range(1,n)]\n",
    "        rd=dd[:]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if i+modulo<n-1:\n",
    "                rd[i]+=rd[i+modulo]\n",
    "        s=0\n",
    "        res=0\n",
    "        for i in range(n-k-2,-1,-1):\n",
    "            if k==0:\n",
    "                res+=(dd[i]-1)*(dd[i])//2\n",
    "                res+=dd[i]*rd[i+modulo] if i+modulo<n-1 else 0\n",
    "            else:\n",
    "                res+=(dd[i])*(rd[i+k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        length = len(nums)\n",
    "        indexes = [-1]\n",
    "        for index, num in enumerate(nums):\n",
    "            if num % modulo == k:\n",
    "                indexes.append(index)\n",
    "        indexes.append(length)\n",
    "\n",
    "        indexes_len = len(indexes)\n",
    "        cnts = [0]*(indexes_len - 1)\n",
    "        cnts_sum = [0]*(indexes_len - 1)\n",
    "        for i in range(indexes_len-1):\n",
    "            cnts[i] = indexes[i+1] - indexes[i]\n",
    "            cnts_sum[i] = cnts[i]\n",
    "        for i in range(indexes_len-1, -1, -1):\n",
    "            if i+modulo < indexes_len - 1:\n",
    "                cnts_sum[i] += cnts_sum[i+modulo]\n",
    "        \n",
    "        # print(indexes_len)\n",
    "        # print(cnts)\n",
    "        # print(cnts_sum)\n",
    "\n",
    "        ans = 0\n",
    "        if k > 0:\n",
    "            for i in range(indexes_len-1):\n",
    "                if i+k < indexes_len-1:\n",
    "                    ans += cnts[i] * cnts_sum[i+k]\n",
    "                else:\n",
    "                    break\n",
    "        else:\n",
    "            for i in range(indexes_len-1):\n",
    "                if i+modulo < indexes_len - 1:\n",
    "                    ans += cnts[i] * cnts_sum[i+modulo]\n",
    "                ans += (cnts[i]*(cnts[i]-1))>>1\n",
    "            pass\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        c = [0] * n\n",
    "        l = [0] * n\n",
    "        prev_match = -1\n",
    "        index = []\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for i,val in enumerate(nums):\n",
    "            if val % modulo != k:                \n",
    "                c[i] = c[i-1] if i > 0 else 0\n",
    "                res += c[i]\n",
    "                cnt += 1\n",
    "                if not k:\n",
    "                    res += cnt\n",
    "                continue\n",
    "            cnt = 0\n",
    "            l[i] = i - prev_match\n",
    "            prev_match = i\n",
    "            index.append(i)\n",
    "            r = k if k else modulo\n",
    "            if len(index) > modulo:\n",
    "                pos = index[-modulo-1]\n",
    "                c[i] += c[pos]\n",
    "            if len(index) >= r:\n",
    "                pos = index[-r]\n",
    "                c[i] += l[pos]\n",
    "            res += c[i]\n",
    "            #print(i, val, ':', c[i], l[i], index)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = 1 if nums[i] % modulo == k else 0\n",
    "        c = Counter()\n",
    "        c[0] += 1\n",
    "        sum_d = 0\n",
    "        for i in nums:\n",
    "            sum_d += i\n",
    "            need = (sum_d % modulo + modulo - k) % modulo\n",
    "            if need in c:\n",
    "                res += c[need]\n",
    "            c[sum_d % modulo] += 1\n",
    "        return res\n",
    "                    \n",
    "            \n",
    "            \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        for i, num in enumerate(nums):\n",
    "            nums[i] = int(num % modulo == k)\n",
    "        \n",
    "        acc = 0\n",
    "        # print(nums, acc)\n",
    "        ans = 0\n",
    "        cnt = Counter([0])\n",
    "        for num in nums:\n",
    "            acc += num\n",
    "            ans += cnt[(acc - k) % modulo]\n",
    "            cnt[acc % modulo] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        mp = {}\n",
    "        pre ,ans = 0 ,0\n",
    "        mp[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums[i] % modulo == k\n",
    "            pre += nums[i]\n",
    "            if (pre-k+modulo)%modulo in mp : ans += mp[(pre-k+modulo)%modulo]\n",
    "            if pre%modulo in mp : mp[pre%modulo] += 1\n",
    "            else : mp[pre%modulo] = 1\n",
    "        print(nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        vis = dict()\n",
    "        def add(num, vis):\n",
    "            if num in vis:\n",
    "                vis[num] += 1\n",
    "            else:\n",
    "                vis[num] = 1\n",
    "        for i in range(n):\n",
    "            nums[i] = 1 if (nums[i]%modulo)==k else 0\n",
    "            if i > 0:\n",
    "                nums[i] = (nums[i-1] + nums[i]) % modulo\n",
    "            nums[i] %= modulo\n",
    "            add(nums[i], vis)\n",
    "            \n",
    "        print(nums)\n",
    "        print(vis)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            target = (k+nums[i-1])%modulo if i > 0 else k\n",
    "            print(target)\n",
    "            ans += vis[target] if target in vis else 0\n",
    "            vis[nums[i]] -= 1\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as dd\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        memo = dd(int)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % modulo == k:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "        pre = [0]\n",
    "        memo[0] = 1\n",
    "        for n in nums:\n",
    "            pre.append((pre[-1]+n)%modulo)\n",
    "        ans = 0\n",
    "        for i in range(1, len(pre)):\n",
    "            res = pre[i]\n",
    "            target = (res - k) % modulo\n",
    "            if target in memo:\n",
    "                ans += memo[target]\n",
    "            memo[res] += 1\n",
    "                # memo[target] += 1\n",
    "            # else:\n",
    "            #     memo[target] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n=len(nums)\n",
    "        l=[]\n",
    "        lst=-1\n",
    "        for i,a in enumerate(nums):\n",
    "            if a%modulo==k:\n",
    "                l.append(i-lst)\n",
    "                lst=i\n",
    "        l.append(n-lst)\n",
    "        g=[[] for _ in range(min(len(l),modulo))]\n",
    "        for i,a in enumerate(l):\n",
    "            i1=i%modulo\n",
    "            g[i1].append(a+(g[i1][-1] if g[i1] else 0))\n",
    "        # print(l)\n",
    "        # print('\\n'.join(map(str,g)))\n",
    "        res=0\n",
    "        for i in range(len(l)):\n",
    "            a,b=divmod(i+k,modulo)\n",
    "            if k==0:\n",
    "                res+=l[i]*(l[i]-1)//2\n",
    "                a+=1\n",
    "            if b<len(l) and g[b]:\n",
    "                res+=l[i]*(g[b][-1]-(g[b][min(len(g[b])-1,a-1)] if a else 0))\n",
    "            # print(i,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], m: int, k: int) -> int:\n",
    "        if m == 1:\n",
    "            return len(nums)*(len(nums)+1)//2\n",
    "        res = 0; h = Counter([0]); s = 0\n",
    "        for i in nums:\n",
    "            s += i%m == k\n",
    "            res += h[(s - k) % m] # 余数为x的加入res 一开始什么都没有\n",
    "            h[s%m] += 1 #同步填充 h\n",
    "        return res\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countInterestingSubarrays(self, nums: List[int], mod: int, k: int) -> int:\n",
    "\n",
    "        cnt = Counter([0])  # 把 s[0]=0 算进去\n",
    "\n",
    "        ans = s = 0\n",
    "\n",
    "        for x in nums:\n",
    "\n",
    "            s += x % mod == k\n",
    "\n",
    "            ans += cnt[(s - k) % mod]  # Python 取模可以把负数自动转成非负数\n",
    "\n",
    "            cnt[s % mod] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%modulo==k:\n",
    "                nums[i]=1\n",
    "            else:\n",
    "                nums[i]=0\n",
    "        L=[0,nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i]+=nums[i-1]\n",
    "            L.append(nums[i])\n",
    "        nums=L\n",
    "        dic=dict()\n",
    "        count=0\n",
    "        for i in range(len(nums)):\n",
    "            count+=dic.get((nums[i]+modulo-k)%modulo,0)\n",
    "            dic[nums[i]%modulo]=dic.get((nums[i])%modulo,0)+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%modulo==k:\n",
    "                nums[i]=1\n",
    "            else:\n",
    "                nums[i]=0\n",
    "        L=[0,nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i]+=nums[i-1]\n",
    "            L.append(nums[i])\n",
    "        nums=L\n",
    "        dic=dict()\n",
    "        count=0\n",
    "        for i in range(len(nums)):\n",
    "            count+=dic.get((nums[i]+modulo-k)%modulo,0)\n",
    "            dic[nums[i]%modulo]=dic.get((nums[i])%modulo,0)+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        d = [1 if num % modulo == k else 0 for num in nums]\n",
    "        \n",
    "        prev = 0\n",
    "        h = {0: 1}\n",
    "        ans = 0\n",
    "        for i in d:\n",
    "            prev += i\n",
    "            prev = prev % modulo\n",
    "            if (prev - k) % modulo in h:\n",
    "                ans += h[(prev - k) % modulo ]\n",
    "            h[prev] = h.get(prev, 0) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        # we only need to care whether nums[i] % modulo == k\n",
    "        arr = [int(x%modulo == k) for x in nums]\n",
    "        \n",
    "        psum = [0]\n",
    "        \n",
    "        for x in arr:\n",
    "            psum.append((psum[-1] + x)%modulo)\n",
    "        \n",
    "        res = 0\n",
    "        cntr = Counter()\n",
    "        for x in psum:\n",
    "            res += cntr[(x-k)%modulo]\n",
    "            cntr[x] += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "s = Solution()\n",
    "    \n",
    "    \n",
    "# example test cases\n",
    "assert s.countInterestingSubarrays(nums = [3,2,4], modulo = 2, k = 1) == 3\n",
    "assert s.countInterestingSubarrays(nums = [3,1,9,6], modulo = 3, k = 0) == 2\n",
    "assert s.countInterestingSubarrays(nums = [0, 0, 0, 0], modulo = 10**9, k = 10**9 - 1) == 0\n",
    "\n",
    "# minimal test cases\n",
    "s.countInterestingSubarrays(nums = [1], modulo = 1, k = 0)\n",
    "\n",
    "# maximal test cases\n",
    "s.countInterestingSubarrays(nums = [10**9]*10**5, modulo = 10**9, k = 10**9-1)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        arr = []\n",
    "        for v in nums:\n",
    "            if v % modulo == k:\n",
    "                arr.append(1)\n",
    "            else:\n",
    "                arr.append(0)\n",
    "\n",
    "        n = len(arr)\n",
    "        S = arr[::]\n",
    "        for i in range(1, n):\n",
    "            S[i] += S[i-1]\n",
    "        for i in range(n):\n",
    "            S[i] %= modulo\n",
    "\n",
    "        cnt = Counter()\n",
    "        cnt[0] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            v = S[i]\n",
    "            if v >= k:\n",
    "                other = v - k\n",
    "            else:\n",
    "                other = v + modulo - k\n",
    "\n",
    "            if other in cnt.keys():\n",
    "                ans += cnt[other]\n",
    "\n",
    "            cnt[S[i]] += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        cnt = Counter({0: 1})\n",
    "        for i, num in enumerate(nums):\n",
    "            cur = 1 if num % modulo == k else 0\n",
    "            v = pre_sum[i + 1] = pre_sum[i] + cur\n",
    "            vr = v % modulo\n",
    "            pr = vr - k\n",
    "            if pr < 0: pr += modulo\n",
    "            ans += cnt[pr]\n",
    "            cnt[vr] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n=len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        cnt=Counter()\n",
    "        ans=0\n",
    "        cnt[0]=1\n",
    "        for i,x in enumerate(nums):\n",
    "            pre[i+1]=pre[i]+(x%modulo==k)\n",
    "            ans+=cnt[(pre[i+1]%modulo-k+modulo)%modulo]\n",
    "            cnt[pre[i+1]%modulo]+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            pre[i+1] = pre[i]+(x%modulo == k)\n",
    "        d = {}\n",
    "        ans = 0\n",
    "        for s in pre:\n",
    "            try:\n",
    "                ans += d[(s%modulo-k+modulo)%modulo]\n",
    "            except:\n",
    "                ans += 0\n",
    "            try:\n",
    "                d[s%modulo] += 1\n",
    "            except:\n",
    "                d[s%modulo] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        nums_len = len(nums)\n",
    "        pre_sum = [0 for i in range(nums_len+1)]\n",
    "        res = 0\n",
    "        counter = {0 : 1}\n",
    "        # 先判断哪些元素满足nums[i] % modulo == k\n",
    "        for i in range(nums_len):\n",
    "            # 维护前缀和列表\n",
    "            if nums[i] % modulo == k:\n",
    "                pre_sum[i+1] = pre_sum[i] + 1\n",
    "            else:\n",
    "                pre_sum[i+1] = pre_sum[i]\n",
    "\n",
    "            # 由于pre_sum[j] % modulo = (pre_sum[i+1]-k) % modulo，即只需要维护 pre_sum[j] % modulo 的值以及数量即可\n",
    "            res += counter.get((pre_sum[i + 1] - k) % modulo, 0)\n",
    "            counter[pre_sum[i+1] % modulo] = counter.get(pre_sum[i+1] % modulo, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums, modulo, k):\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        preSum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + (1 if nums[i] % modulo == k else 0)\n",
    "        count_map = {}\n",
    "        for i in range(n + 1):\n",
    "            key = (preSum[i] % modulo - k + modulo) % modulo\n",
    "            if key in count_map:\n",
    "                ans += count_map[key]\n",
    "            count_map[preSum[i] % modulo] = count_map.get(preSum[i] % modulo, 0) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        tl=[int(tn%modulo==k) for tn in nums]\n",
    "        acc_l=list(accumulate(tl,initial=0))\n",
    "\n",
    "        cnt=Counter()\n",
    "        tans=0\n",
    "        for x in acc_l:\n",
    "            tans+=cnt[(x)%modulo]\n",
    "            cnt[(x+k)%modulo]+=1\n",
    "        return tans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        mod_ret = list(1 if x % modulo == k else 0 for x in nums)\n",
    "        acc = [0] + list(accumulate(mod_ret))\n",
    "        \n",
    "        acc = list(x % modulo for x in acc)\n",
    "        cnt = Counter(acc)\n",
    "        ret = 0\n",
    "        # print(acc)\n",
    "        for i, l in enumerate(acc):\n",
    "            cnt[l] -= 1\n",
    "            ret += cnt[((l % modulo + modulo) % modulo + k) % modulo]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        f = [int(x % modulo == k) for x in nums]\n",
    "        pref = [0] + list(accumulate(f))\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x in pref:\n",
    "            ans += cnt[(x - k + modulo) % modulo]\n",
    "            cnt[x % modulo] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "并没有数学公式的推导，而是将问题转换\n",
    "如果nums[i]%m==k-->nums[i]=1,否则nums[i]=0\n",
    "转换成前缀和即可快速算出cnt\n",
    "\n",
    "但是暴力枚举子数组端点肯定不行，使用哈希表加速即可，起飞\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], m: int, k: int) -> int:\n",
    "        '''\n",
    "        复习一下accumulate\n",
    "        0 1 2 3 3 4 6 8\n",
    "        '''\n",
    "        nums_=[0]*len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x%m==k:\n",
    "                nums_[i]=1\n",
    "            else:nums_[i]=0\n",
    "        s=list(accumulate(nums_,initial=0))\n",
    "        #接下来应该是模运算严格的数学公式推导，不是简单的看样例\n",
    "\n",
    "        cnt=Counter([0])\n",
    "        ans=0\n",
    "        for x in s[1:]:\n",
    "            ans+=cnt[(x-k)%m]\n",
    "            cnt[x%m]+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Dict\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], M: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def judge(a):\n",
    "            if a % M == k:\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        lables = []\n",
    "        for num in nums:\n",
    "            lables.append(judge(num))\n",
    "        pre_sum = [0]\n",
    "        table = {0:1}\n",
    "        table_list = [1]\n",
    "        for i, l in enumerate(lables):\n",
    "            if l == 0:\n",
    "                table_list[-1] += 1\n",
    "            else:\n",
    "                table_list.append(1)\n",
    "            pre_sum.append(l+pre_sum[-1])\n",
    "        max_num = len(table_list) - 1\n",
    "        memory = {}\n",
    "        if k == 0:\n",
    "            for start in range(len(table_list)):\n",
    "                start_count = table_list[start]\n",
    "                end = start + M\n",
    "                if start % M in memory:\n",
    "                    memory[start % M] = memory[start % M] - table_list[start]\n",
    "\n",
    "                    end_count = memory[start % M]\n",
    "                else:\n",
    "                    end_count = 0\n",
    "                    while 1:\n",
    "                        if end > max_num:\n",
    "                            break\n",
    "                        else:\n",
    "                            end_count += table_list[end]\n",
    "                            end += M\n",
    "                            memory[start % M] = end_count\n",
    "                ans += start_count * end_count + start_count * (start_count-1) // 2\n",
    "        else:\n",
    "            for start in range(len(table_list)):\n",
    "                start_count = table_list[start]\n",
    "                end = start + k\n",
    "                if start % M in memory:\n",
    "                    memory[start % M] = memory[start % M] - table_list[start + k - M]\n",
    "                    end_count = memory[start % M]\n",
    "                else:\n",
    "                    end_count = 0\n",
    "                    while 1:\n",
    "                        if end > max_num:\n",
    "                            break\n",
    "                        else:\n",
    "                            end_count += table_list[end]\n",
    "                            end += M\n",
    "                    memory[start % M] = end_count\n",
    "\n",
    "                ans += start_count * end_count\n",
    "\n",
    "        # dones = set()\n",
    "        # if k == 0:\n",
    "        #     last_pre_sum = -1\n",
    "        #     for i in range(n):\n",
    "        #         if last_pre_sum != pre_sum[i]:\n",
    "        #             kkk = table[pre_sum[i]]\n",
    "        #             ans += kkk * (kkk - 1) // 2\n",
    "        #             last_pre_sum = pre_sum[i]\n",
    "        #         base = pre_sum[i] + M\n",
    "        #         tmp = 0\n",
    "        #         while 1:\n",
    "        #             if base in table:\n",
    "        #                 tmp += table[base]\n",
    "        #                 base += M\n",
    "        #             else:\n",
    "        #                 ans += tmp\n",
    "        #                 break\n",
    "        # else:\n",
    "        #     for i in range(n):\n",
    "        #         base = pre_sum[i] + k\n",
    "        #         ak = 0\n",
    "        #         tmp = 0\n",
    "        #         while 1:\n",
    "        #             if base in table:\n",
    "        #                 tmp += table[base]\n",
    "        #                 base += M\n",
    "        #\n",
    "        #             else:\n",
    "        #                 ans += tmp\n",
    "        #                 break\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    # print(s.countInterestingSubarrays([3,1,9,6], 3, 0))\n",
    "    # print(s.countInterestingSubarrays([3,2,4], 2, 1))\n",
    "    # print(s.countInterestingSubarrays([2,7], 7, 0))\n",
    "    # print(s.countInterestingSubarrays([5, 2,8], 2, 0))\n",
    "    # print(s.countInterestingSubarrays([25,26,22,48,37,40,34], 2, 0))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        is_fun = [0] * n\n",
    "        for i in range(n):\n",
    "            if nums[i] % modulo == k:\n",
    "                is_fun[i] = 1\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = presum[i] + is_fun[i]\n",
    "        presum_mod = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum_mod[i + 1] = presum[i + 1] % modulo\n",
    "        presum_mod_counter = Counter(presum_mod)\n",
    "        #枚举左端点\n",
    "        for i in range(n):\n",
    "            current_mdd = presum_mod[i]\n",
    "            presum_mod_counter[current_mdd] -= 1\n",
    "            target_mdd = (current_mdd + k) % modulo\n",
    "            ans += presum_mod_counter[target_mdd]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        is_interest = list(map(lambda x: x%modulo==k, nums))\n",
    "\n",
    "\n",
    "        ss = [0] * n\n",
    "        if is_interest[0]:\n",
    "            ss[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if is_interest[i]:\n",
    "                ss[i] = ss[i - 1] + 1\n",
    "            else:\n",
    "                ss[i] = ss[i - 1]\n",
    "\n",
    "        rem_i = list(map(lambda x: x%modulo, ss))\n",
    "        # print(rem_i)\n",
    "        c = {}\n",
    "        cr = [0]*n\n",
    "        i = 0\n",
    "        for r in rem_i:\n",
    "            cr[i] = c.get((r - k)%modulo, 0)\n",
    "            if r in c:\n",
    "                c[r] += 1\n",
    "            else:\n",
    "                c[r] = 1\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return sum(cr)+rem_i.count(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        @cache\n",
    "        def mod(x):\n",
    "            return x%modulo\n",
    "        @cache\n",
    "        def fun(x):\n",
    "            return 1 if mod(x) == k else 0\n",
    "        \n",
    "        rwlist = [fun(x) for x in nums]  #10列表，判断是不是\n",
    "        m = modulo; res = 0; h = Counter()\n",
    "        h[0] = 1    ##啥也没有，即[] 也是一个情况\n",
    "        s = 0\n",
    "        for i in rwlist:\n",
    "            s = (s+i) % m #mod余数\n",
    "            x = (s -k +m ) % m ##x就是 mod验证 如果x = 0 说明符合 条件  s % m = k\n",
    "            res += h[x] # 余数为x的加入res 一开始什么都没有\n",
    "            h[s] += 1 #同步填充 h\n",
    "        return res\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], mod: int, k: int) -> int:\n",
    "        # sum[l,r]%mod = k s[r]-s[l]= k  (mod) \n",
    "        # sr = sl+k  (mod)       \n",
    "         \n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = 0 if (nums[i]%mod)!=k else 1\n",
    "        s = 0\n",
    "        cnt = defaultdict(lambda:0)\n",
    "        cnt[0]=1\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            s+=n\n",
    "            s = s%mod\n",
    "            t=(s-k)%mod\n",
    "            if cnt[t]:\n",
    "                ans+=cnt[t]\n",
    "            cnt[s]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] = nums[i]%modulo==k\n",
    "        preSum = 0\n",
    "        # print(nums)\n",
    "        store = {0:[-1]}\n",
    "        for i, n in enumerate(nums):\n",
    "            preSum += n\n",
    "            tmp = preSum%modulo\n",
    "            if tmp not in store:\n",
    "                store[tmp] = []\n",
    "            store[tmp].append(i)\n",
    "        ans = 0\n",
    "        # print(store)\n",
    "        for kk, v in store.items():\n",
    "            for i in v:\n",
    "                tmpkk = kk-k\n",
    "                if tmpkk<0:\n",
    "                    tmpkk += modulo\n",
    "                tmpIdx = bisect.bisect_right(store.get(tmpkk, []), i)\n",
    "                if k==0:\n",
    "                    ans += tmpIdx-1\n",
    "                else:\n",
    "                    ans += tmpIdx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        idxs = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if num % modulo == k:\n",
    "                idxs.append(i)\n",
    "        l = []\n",
    "        r = []\n",
    "        pre = -1\n",
    "        for i in idxs:\n",
    "            l.append(i - pre)\n",
    "            pre = i\n",
    "        aft = len(nums)\n",
    "        for i in idxs[::-1]:\n",
    "            r.append(aft - i)\n",
    "            aft = i\n",
    "        r = r[::-1]\n",
    "        \n",
    "        st = []\n",
    "        for i in range(k - 1, len(idxs), modulo):\n",
    "            if i >= 0:\n",
    "                st.append(i)\n",
    "        lst = len(st)\n",
    "        dic = {}\n",
    "        for i in range(lst):\n",
    "            for j in range(st[i], min(len(idxs), st[i] + modulo)):\n",
    "                dic[j] = j - st[i]\n",
    "        sums = collections.defaultdict(int)\n",
    "        for i in range(len(idxs)):\n",
    "            if i in dic:\n",
    "                sums[dic[i]] += r[i]\n",
    "        res = 0\n",
    "        if st:\n",
    "            ii = st[0]\n",
    "            for i, idx in enumerate(idxs):\n",
    "                res += l[i] * sums[i % modulo]\n",
    "                if ii in dic:\n",
    "                    sums[dic[ii]] -= r[ii]\n",
    "                ii += 1\n",
    "        if k == 0:\n",
    "            idxs = [-1] + idxs + [len(nums)]\n",
    "            for i in range(1, len(idxs)):\n",
    "                diff = idxs[i] - idxs[i - 1]\n",
    "                if diff > 1:\n",
    "                    res += diff * (diff - 1) // 2\n",
    "        \n",
    "        \n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        pre = [0]\n",
    "        counter = defaultdict(int)\n",
    "        counter[0] = 1\n",
    "        ans = 0\n",
    "\n",
    "        for i in nums:\n",
    "            cur = (pre[-1] + (1 if i % modulo == k else 0)) % modulo\n",
    "            pre.append(cur)\n",
    "            d = (cur - k + modulo) % modulo\n",
    "            ans += counter[d]\n",
    "            counter[cur] += 1\n",
    "        # print(counter)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        s = res = 0\n",
    "        for x in nums:\n",
    "            if x % modulo == k:\n",
    "                s = (s + 1) % modulo\n",
    "            res += cnt[(s - k + modulo) % modulo]\n",
    "            cnt[s%modulo] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], mod: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        hash_map = defaultdict(int)\n",
    "        hash_map[0] = 1\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            # print(hash_map)\n",
    "            if x % mod == k:\n",
    "                cnt += 1\n",
    "            # print((k-cnt%mod)%mod)\n",
    "            ans += hash_map[(cnt-k)%mod]\n",
    "            hash_map[cnt%mod] += 1\n",
    "        # print(' ')\n",
    "        # print(hash_map)\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        cnt, res = defaultdict(int), 0\n",
    "        for x in accumulate((x % modulo == k for x in nums), initial=0):\n",
    "            res += cnt[(x - k) % modulo]\n",
    "            cnt[x % modulo] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        dic[0].append(-1)\n",
    "        tmp = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%modulo==k:\n",
    "                tmp+=1\n",
    "                tmp %= modulo\n",
    "            dic[tmp].append(i)\n",
    "        res = 0\n",
    "        for i in dic:\n",
    "            if (i-k)%modulo in dic:\n",
    "                a,b = dic[(i-k)%modulo],dic[i]\n",
    "                index = -1\n",
    "                for j in b:\n",
    "                    while index+1<len(a) and a[index+1]<j:\n",
    "                        index+=1\n",
    "                    res+=index+1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        # from itertools import accumulate\n",
    "        # presums = list(accumulate([1 if x % modulo == k else 0 for x in nums], initial=0))\n",
    "        # ans = 0\n",
    "        # d = defaultdict(int)\n",
    "        # for x in presums:\n",
    "        #     if (x - k) % modulo in d:\n",
    "        #         ans += d[(x - k) % modulo]\n",
    "        #     d[x % modulo] += 1\n",
    "        # return ans\n",
    "\n",
    "        nums2 = list([1 if x % modulo == k else 0 for x in nums])\n",
    "        ans = 0\n",
    "        presums = defaultdict(int)\n",
    "        presums[0] = 1\n",
    "        presum = 0\n",
    "        for x in nums2:\n",
    "            presum = (presum + x) % modulo\n",
    "            ans += presums[(presum - k) % modulo]\n",
    "            presums[presum] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        nums = [1 if n % modulo == k else 0 for n in nums]\n",
    "        sm = [0]\n",
    "        for n in nums:\n",
    "            sm.append((sm[-1] + n) % modulo)\n",
    "        # print(sm)\n",
    "        # cnt = Counter(sm)\n",
    "        # print(cnt)\n",
    "        res = 0\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        for i in range(1, len(sm)):\n",
    "            res += cnt[(sm[i] - k) % modulo]\n",
    "            cnt[sm[i]] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        t = [0] * n\n",
    "        for i in range(n):\n",
    "            if nums[i] % modulo == k:\n",
    "                t[i] = 1\n",
    "        ans = 0\n",
    "        preSum = list(accumulate(t, initial = 0))\n",
    "        #print(preSum)\n",
    "        for i in range(n + 1):\n",
    "            preSum[i] %= modulo\n",
    "        d = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            pre = (preSum[i] - k) % modulo\n",
    "            ans += d[pre]\n",
    "            d[preSum[i]] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        cntSum = defaultdict(int)\n",
    "        cntSum[0] += 1\n",
    "        \n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cnt += num % modulo == k\n",
    "            cnt %= modulo\n",
    "            ans += cntSum[cnt - k] + cntSum[cnt + modulo - k]\n",
    "            cntSum[cnt] += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], m: int, k: int) -> int:\n",
    "        vs = [1 if v % m == k else 0 for v in nums]\n",
    "        ps = [0]\n",
    "        sm = 0\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        ans = 0\n",
    "        for v in vs:\n",
    "            sm += v\n",
    "            sm %= m \n",
    "            ps.append(sm)\n",
    "        \n",
    "        for v in ps[1:]:\n",
    "            ans += cnt[(v-k)%m]\n",
    "            # print(ans, sm, a:=(v-k)%m, cnt[a])\n",
    "            cnt[v] += 1\n",
    "        # print(ps)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        csum = [0]\n",
    "        t = 0\n",
    "        ret = 0\n",
    "        count = defaultdict(lambda: 0)\n",
    "        count[0] = 1\n",
    "        for num in nums:\n",
    "            t += int(num % modulo == k)\n",
    "            csum.append(t)\n",
    "            ret += count[(t - k) % modulo]\n",
    "            count[t % modulo] += 1\n",
    "        #print(csum)\n",
    "        #print(count)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "\n",
    "        count = defaultdict(int)\n",
    "        count[0] = 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + (1 if nums[i] % modulo == k else 0)\n",
    "            res += count[(pre[i+1]-k)%modulo]\n",
    "            count[pre[i+1]%modulo] += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        intersting_subarrays = 0\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + (nums[i] % modulo == k)\n",
    "        \n",
    "        hs = defaultdict(int)\n",
    "        for i in range(n + 1):\n",
    "            intersting_subarrays += hs[(prefix_sum[i] - k + modulo) % modulo]\n",
    "            hs[prefix_sum[i] % modulo] += 1\n",
    "                \n",
    "        return intersting_subarrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:\n",
    "        pre=[0]*(len(nums)+1)\n",
    "        res=0\n",
    "        import collections\n",
    "        s=collections.defaultdict(int)\n",
    "        s[0]=1\n",
    "        flag=[0 for i in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%modulo==k:\n",
    "                flag[i]=1\n",
    "            pre[i+1]=pre[i]+flag[i]\n",
    "            res+=s[(pre[i+1]-k)%modulo]\n",
    "            s[pre[i+1]%modulo]+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countInterestingSubarrays(self, s, m: int, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] + [1 if v % m == k else 0 for v in s]\n",
    "        f = list(itertools.accumulate(f))\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans += mp[(f[i] - k + m) % m]\n",
    "            mp[f[i] % m] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
